package com.gitee.feizns.explore.data_structure.tree.cus;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.function.BiConsumer;

/**
 * @author feizns
 * @since 2019/11/28
 */
public interface BinaryTree<N extends Node, K extends Comparable<K>, V> extends Tree<K, V> {

    /**
     * 根节点
     * @return
     */
    Node root();

    /**
     * 递归前序遍历
     * @param consumer
     */
    default void recursiveBeforeEach(BiConsumer<K, V> consumer) {
        recursiveBeforeEach(root(), consumer);
    }

    /**
     * 递归前序遍历
     * @param node
     * @param consumer
     */
    default void recursiveBeforeEach(Node<N, K, V> node, BiConsumer<K, V> consumer) {
        if ( node != null ) {
            consumer.accept(node.key(), node.val());
            recursiveBeforeEach(node.left(), consumer);
            recursiveBeforeEach(node.right(), consumer);
        }
    }

    /**
     * 递归中序遍历
     * @param consumer
     */
    default void recursiveMiddleEach(BiConsumer<K, V> consumer) {
        recursiveMiddleEach(root(), consumer);
    }

    default void recursiveMiddleEach(Node<N, K, V> node, BiConsumer<K, V> consumer) {
        if ( node != null ) {
            recursiveMiddleEach(node.left(), consumer);
            consumer.accept(node.key(), node.val());
            recursiveMiddleEach(node.right(), consumer);
        }
    }

    /**
     * 递归后序遍历
     * @param consumer
     */
    default void recursiveAfterEach(BiConsumer<K, V> consumer) {
        recursiveAfterEach(root(), consumer);
    }

    default void recursiveAfterEach(Node<N, K, V> node, BiConsumer<K, V> consumer) {
        if ( node != null ) {
            recursiveAfterEach(node.left(), consumer);
            recursiveAfterEach(node.right(), consumer);
            consumer.accept(node.key(), node.val());
        }
    }

    /**
     * 递归层序遍历
     * @param consumer
     */
    default void recursiveSequenceTraversal(BiConsumer<K, V> consumer) {
        Node<N, K, V> root = root();
        if ( root != null ) {
            Queue<Node<N, K, V>> queue = new LinkedList<>();
            queue.add(root);
            recursiveSequenceTraversal(queue, consumer);
        }
    }

    default void recursiveSequenceTraversal(Queue<Node<N, K, V>> queue, BiConsumer<K, V> consumer) {
        Queue<Node<N, K, V>> newQueue = new LinkedList<>();
        TreeUtils.sequenceTraversal(queue, consumer, newQueue::add);
        if ( !newQueue.isEmpty() )
            recursiveSequenceTraversal(newQueue, consumer);
    }

    /**
     * 非递归前序遍历
     * @param consumer
     */
    default void beforeEach(BiConsumer<K, V> consumer) {
        Node<N, K, V> root = root();
        Stack<Node<N, K, V>> stack = new Stack<>();
        if ( root != null )
            stack.push(root);
        while ( !stack.isEmpty() ) {
            Node<N, K, V> node = stack.pop();
            consumer.accept(node.key(), node.val());
            if ( node.right() != null )
                stack.push(node.right());
            if ( node.left() != null )
                stack.push(node.left());
        }
    }

    /**
     * 非递归中序遍历
     * @param consumer
     */
    default void middleEach(BiConsumer<K, V> consumer) {
        middleEach(root(), consumer);
    }

    default void middleEach(Node<N, K, V> root, BiConsumer<K, V> consumer) {
        Stack<Node<N, K, V>> stack = new Stack<>();
        while ( root != null || !stack.isEmpty() ) {
            while ( root != null ) {
                stack.push(root);
                root = root.left();
            }
            Node<N, K, V> node = stack.pop();
            consumer.accept(node.key(), node.val());
            if ( node.right() != null )
                root = node.right();
        }
    }

    /**
     * 非递归后序遍历
     * @param consumer
     */
    default void afterEach(BiConsumer<K, V> consumer) {
        afterEach(root(), consumer);
    }

    default void afterEach(Node<N, K, V> root, BiConsumer<K, V> consumer) {
        Stack<Node<N, K, V>> stack = new Stack<>();
        Stack<Node<N, K, V>> retStack = new Stack<>();

        stack.push(root);
        while ( !stack.isEmpty() ) {
            Node<N, K, V> node = stack.pop();
            retStack.push(node);
            if ( node.left() != null )
                stack.push(node.left());
            if ( node.right() != null )
                stack.push(node.right());
        }

        while ( !retStack.isEmpty() ) {
            Node<N, K, V> node = retStack.pop();
            consumer.accept(node.key(), node.val());
        }
    }

    /**
     * 非递归层序遍历
     * @param consumer
     */
    default void sequenceTraversal(BiConsumer<K, V> consumer) {
        TreeUtils.sequenceTraversal(root(), consumer);
    }

}
